home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / • Other Platforms / PCCTS 1.31 / antlr / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-10  |  5.3 KB  |  229 lines  |  [TEXT/MPS ]
  1. /*
  2.  * hash.c
  3.  *
  4.  * $Id: hash.c,v 1.8 1994/12/31 21:02:55 parrt Exp parrt $
  5.  * $Revision: 1.8 $
  6.  *
  7.  * Manage hash tables.
  8.  *
  9.  * The following functions are visible:
  10.  *
  11.  *        char    *mystrdup(char *);        Make space and copy string
  12.  *        Entry     **newHashTable();        Create and return initialized hash table
  13.  *        Entry    *hash_add(Entry **, char *, Entry *)
  14.  *        Entry    *hash_get(Entry **, char *)
  15.  *
  16.  * SOFTWARE RIGHTS
  17.  *
  18.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  19.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  20.  * company may do whatever they wish with source code distributed with
  21.  * PCCTS or the code generated by PCCTS, including the incorporation of
  22.  * PCCTS, or its output, into commerical software.
  23.  * 
  24.  * We encourage users to develop software with PCCTS.  However, we do ask
  25.  * that credit is given to us for developing PCCTS.  By "credit",
  26.  * we mean that if you incorporate our source code into one of your
  27.  * programs (commercial product, research project, or otherwise) that you
  28.  * acknowledge this fact somewhere in the documentation, research report,
  29.  * etc...  If you like PCCTS and have developed a nice tool with the
  30.  * output, please mention that you developed it using PCCTS.  In
  31.  * addition, we ask that this header remain intact in our source code.
  32.  * As long as these guidelines are kept, we expect to continue enhancing
  33.  * this system and expect to make other tools available as they are
  34.  * completed.
  35.  *
  36.  * ANTLR 1.31
  37.  * Terence Parr
  38.  * Parr Research Corporation
  39.  * with Purdue University and AHPCRC, University of Minnesota
  40.  * 1989-1995
  41.  */
  42.  
  43. #include <stdio.h>
  44. #ifdef __cplusplus
  45. #ifndef __STDC__
  46. #define __STDC__
  47. #endif
  48. #endif
  49. #include "hash.h"
  50. #ifdef __STDC__
  51. #include <stdlib.h>
  52. #else
  53. #ifdef VAXC
  54. #include <stdlib.h>
  55. #else
  56. #include <malloc.h>
  57. #endif
  58. #endif
  59. #include <string.h>
  60.  
  61. #define StrSame        0
  62.  
  63. #define fatal(err)                                                            \
  64.             {fprintf(stderr, "%s(%d):", __FILE__, __LINE__);                \
  65.             fprintf(stderr, " %s\n", err); exit(1);}
  66. #define require(expr, err) {if ( !(expr) ) fatal(err);}
  67.  
  68. static unsigned size = HashTableSize;
  69. static char *strings = NULL;
  70. static char *strp;
  71. static unsigned strsize = StrTableSize;
  72.  
  73. /* create the hash table and string table for terminals (string table only once) */
  74. Entry **
  75. #ifdef __STDC__
  76. newHashTable( void )
  77. #else
  78. newHashTable( )
  79. #endif
  80. {
  81.     Entry **table;
  82.     
  83.     table = (Entry **) calloc(size, sizeof(Entry *));
  84.     require( table != NULL, "cannot allocate hash table");
  85.     if ( strings == NULL )
  86.     {
  87.         strings = (char *) calloc(strsize, sizeof(char));
  88.         require( strings != NULL, "cannot allocate string table");
  89.         strp = strings;
  90.     }
  91.     return table;
  92. }
  93.  
  94. void
  95. #ifdef __STDC__
  96. killHashTable( Entry **table )
  97. #else
  98. killHashTable( table )
  99. Entry **table;
  100. #endif
  101. {
  102.     /* for now, just free table, forget entries */
  103.     free( table );
  104. }
  105.  
  106. /* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */
  107. Entry *
  108. #ifdef __STDC__
  109. hash_add( Entry **table, char *key, Entry *rec )
  110. #else
  111. hash_add( table, key, rec )
  112. Entry **table;
  113. char *key;
  114. Entry *rec;
  115. #endif
  116. {
  117.     unsigned h=0;
  118.     char *p=key;
  119.     extern Entry *Globals;
  120.     require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");
  121.     
  122.     Hash(p,h,size);
  123.     rec->next = table[h];            /* Add to singly-linked list */
  124.     table[h] = rec;
  125.     return rec;
  126. }
  127.  
  128. /* Return ptr to 1st entry found in table under key (return NULL if none found) */
  129. Entry *
  130. #ifdef __STDC__
  131. hash_get( Entry **table, char *key )
  132. #else
  133. hash_get( table, key )
  134. Entry **table;
  135. char *key;
  136. #endif
  137. {
  138.     unsigned h=0;
  139.     char *p=key;
  140.     Entry *q;
  141. /*    require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/
  142.     if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3;
  143.     
  144.     Hash(p,h,size);
  145.     for (q = table[h]; q != NULL; q = q->next)
  146.     {
  147.         if ( strcmp(key, q->str) == StrSame ) return( q );
  148.     }
  149.     return( NULL );
  150. }
  151.  
  152. #ifdef DEBUG_HASH
  153. void
  154. #ifdef __STDC__
  155. hashStat( Entry **table )
  156. #else
  157. hashStat( table )
  158. Entry **table;
  159. #endif
  160. {
  161.     static unsigned short count[20];
  162.     int i,n=0,low=0, hi=0;
  163.     Entry **p;
  164.     float avg=0.0;
  165.     
  166.     for (i=0; i<20; i++) count[i] = 0;
  167.     for (p=table; p<&(table[size]); p++)
  168.     {
  169.         Entry *q = *p;
  170.         int len;
  171.         
  172.         if ( q != NULL && low==0 ) low = p-table;
  173.         len = 0;
  174.         if ( q != NULL ) fprintf(stderr, "[%d]", p-table);
  175.         while ( q != NULL )
  176.         {
  177.             len++;
  178.             n++;
  179.             fprintf(stderr, " %s", q->str);
  180.             q = q->next;
  181.             if ( q == NULL ) fprintf(stderr, "\n");
  182.         }
  183.         count[len]++;
  184.         if ( *p != NULL ) hi = p-table;
  185.     }
  186.  
  187.     fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n",
  188.                     n, size-count[0], size);
  189.     fprintf(stderr, "%f %% utilization\n",
  190.                     ((float)(size-count[0]))/((float)size));
  191.     for (i=0; i<20; i++)
  192.     {
  193.         if ( count[i] != 0 )
  194.         {
  195.             avg += (((float)(i*count[i]))/((float)n)) * i;
  196.             fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n",
  197.                             i, count[i], ((float)(i*count[i]))/((float)n));
  198.         }
  199.     }
  200.     fprintf(stderr, "Avg bucket length %f\n", avg);
  201.     fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);
  202. }
  203. #endif
  204.  
  205. /* Add a string to the string table and return a pointer to it.
  206.  * Bump the pointer into the string table to next avail position.
  207.  */
  208. char *
  209. #ifdef __STDC__
  210. mystrdup( char *s )
  211. #else
  212. mystrdup( s )
  213. char *s;
  214. #endif
  215. {
  216.     char *start=strp;
  217.     require(s!=NULL, "mystrdup: NULL string");
  218.  
  219.     while ( *s != '\0' )
  220.     {
  221.         require( strp <= &(strings[strsize-2]),
  222.                  "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");
  223.         *strp++ = *s++;
  224.     }
  225.     *strp++ = '\0';
  226.  
  227.     return( start );
  228. }
  229.